package com.company

fun main() {
    var solution = Solution()
    var r = solution.findMedianSortedArrays(intArrayOf(1), intArrayOf(2,3,4,5,6))
    println(r)
}



class Solution {
    fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
        var num = nums1.size + nums2.size

        var result = if (num % 2 == 1) {
            findK(nums1, nums2, (num + 1)/2).toDouble()
        } else {
            var v1 =  findK(nums1, nums2, (num + 1)/2)
            var v2 =  findK(nums1, nums2, (num + 2)/2)
            (v1 + v2) / 2.0
        }
        return result
    }

    fun findK(nums1: IntArray, nums2: IntArray, kth: Int): Int {
        var l1 = 0;
        var l2 = 0;
        val r1 = nums1.size
        val r2 = nums2.size
        var k = kth
        do {
           if (l1 >= r1) {
               return nums2[l2 + k - 1]
           }

           if (l2 >= r2) {
               return nums1[l1 + k - 1]
           }

            if (k == 1) {
                return Math.min(nums1[l1], nums2[l2])
            }

            var v1 = if(l1 + k/2 -1 < r1) nums1[l1 + k/2 -1]  else nums1[r1 -1]
            var v2 = if(l2 + k/2 -1 < r2) nums2[l2 + k/2 -1]  else nums2[r2 -1]

            if (v1 < v2) {
                l1 += k/2
            } else {
                l2 += k/2
            }
            k = k - k/2
        }while(true)
    }
}